package com.acyouzi.leetcode.greedy;

/**
 * 17/9/7 15:11
 *
 * @author sunxu
 */
public class GasStation {
  // https://leetcode.com/problems/gas-station/description/
  // 注意：题目条件是加油站构成一个环，每次只能到环的下一个节点
  public int canCompleteCircuit(int[] gas, int[] cost) {
    int sum = 0;
    int total = 0;
    int k = 0;
    for (int i = 0; i < gas.length; i++) {
      sum += gas[i] - cost[i];
      if (sum < 0){
        sum = 0;
        k = i+1;
      }
      total += gas[i] - cost[i];
    }
    if (total < 0){
      return -1;
    }else{
      return k;
    }
  }
}
